package top.humbleyuan.backtrack;

/**
 * @Author HumbleYuan
 * @Date 2020/5/18 21:35
 * @Des 戳气球
 */
public class LeetCode_312 {
    public static void main(String[] args) {
        // 暴力回溯
        m1();

        // 带缓存剪枝回溯
        m2();
    }

    public static void m1() {
        int[] nums = {3,1,5,8};
        System.out.println(dfs(nums, 0, 0));
    }

    public static int dfs(int[] nums,int coins, int maxCoin) {
        if(nums.length == 0) {
            // System.out.println(coins);
            if(coins > maxCoin) {
                return coins;
            }
        }

        /**
         * 每次戳一个气球
         * 回溯到上一层时恢复戳破的气球
         */
        for (int i = 0; i < nums.length; i++) {
            int add = 0;
            if(i == 0) {
                add = nums[i] * (nums.length > 1 ? nums[i+1] : 1);
            } else if(i == nums.length - 1) {
                add = nums[i] * (nums.length > 1 ? nums[i-1] : 1);
            }
            else {
                add = nums[i-1] * nums[i] * nums[i+1];
            }
            coins += add;

            int[] newNums = new int[nums.length - 1];
            System.arraycopy(nums, 0, newNums, 0, i - 0);
            System.arraycopy(nums, i + 1, newNums, i, nums.length - 1 - i);
            maxCoin = dfs(newNums, coins, maxCoin);

            // 回溯
            coins -= add;
        }

        return maxCoin;
    }

    /**
     * 带缓存回溯剪枝
     */
    public static void m2() {
        int[] nums = {3,1,5,8};

        // 处理数组，首位加1
        nums = manage(nums);

        int[][] cache = new int[nums.length][nums.length];

        // 回溯 + 缓存
        // 扩充1不影响计算
        System.out.println(getMax(nums, 0, nums.length - 1, cache));
    }

    // 扩充数组边界
    public static int[] manage(int[] nums) {
        int[] newNums = new int[nums.length + 2];
        newNums[0] = newNums[newNums.length - 1] = 1;

        System.arraycopy(nums, 0, newNums, 1, nums.length);
        return newNums;
    }

    // 回溯
    public static int getMax(int[] nums,int begin,int end,int[][] cache) {
        /**
         * 注意下面for循环
         * 当begin,end紧随时
         * i = begin = end
         * 即返回0，只需计算戳破当前气球的收益
         */
        if(begin == end - 1) {
            return 0;
        }

        // 依据缓存
        if(cache[begin][end] != 0) {
            return cache[begin][end];
        }

        int max = 0;
        // begin .. i ..end
        // 这样分治最后肯定是剩余begin,i,end,
        for (int i = begin + 1; i < end; i++) {
            // 计算begin,end = (begin,i) + (i,end)
            int curMax = getMax(nums, begin, i, cache) +
                    getMax(nums, i, end, cache) + nums[begin] * nums[i] * nums[end];

            if(curMax > max) {
                max = curMax;
            }
        }
        cache[begin][end] = max;
        return max;
    }

}
